/*
 * BigInteger.js
 * Represents an Arbitrarily Large Signed Integer.
 * Copyright (C) Jorge H. C. Lucema.
 */

/*global Classic, Barrett, Montgomery, NullExponent */

var dbits, BI_FP, BI_RM, BI_RC, BigInteger, charValue, count;

dbits = 28;
BI_FP = 52;
BI_RM = "0123456789abcdefghijklmnopqrstuvwxyz";
BI_RC = [];
//Numbers 0 - 9
charValue = 48;
count = 0;
while (count <= 9) {
    BI_RC[charValue] = count;
    charValue += 1;
    count += 1;
}
//Uppercase Letters A - Z
charValue = 65;
count = 0;
while (count <= 35) {
    BI_RC[charValue] = count;
    charValue += 1;
    count += 1;
}
//Lowercase Letters a - z
charValue = 97;
count = 0;
while (count <= 35) {
    BI_RC[charValue] = count;
    charValue += 1;
    count += 1;
}

BigInteger = (function () {

    "use strict";
    /**
     * 
     * @param {string} a
     * @param {integer} b
     * @param {integer} c
     * @returns {BigInteger2_L40.BigInteger}
     */
    var BigInteger = function (a, b, c) {
        if (!(this instanceof BigInteger)) {
            return new BigInteger();
        }
        if (a !== null && a !== undefined) {
            if ("number" === typeof a) {
                this.fromNumber(a, b, c);
            } else if (b === null && ("string" !== typeof a)) {
                this.fromString(a, 256);
            } else {
                this.fromString(a, b);
            }
        }
    };

    BigInteger.nbv = function (i) {
        var r = BigInteger();
        r.fromInt(i);
        return r;
    };

    BigInteger.fromNumber = function (a, b, c) {
        if ("number" === typeof b) {
            if (a < 2) {
                this.fromInt(1);
            } else {
                this.fromNumber(a, c);
                //if(!this.testBit(a-1)) this.bitwiseTo(BigInteger.ONE.shiftLeft(a-1), op_or, this); // force MSB set
                if (this.isEven()) {
                    this.dAddOffset(1, 0); // force odd
                }
                while (!this.isProbablePrime(b)) {
                    this.dAddOffset(2, 0);
                    if (this.bitLength() > a) {
                        this.subTo(BigInteger.ONE.shiftLeft(a - 1), this);
                    }
                }
            }
        } else {
            var x = [], t = a & 7;
            x.length = (a >> 3) + 1;
            b.nextBytes(x);
            if (t > 0) {
                x[0] &= ((1 << t) - 1);
            } else {
                x[0] = 0;
            }
            this.fromString(x, 256);
        }
    };

    BigInteger.fromInt = function (x) {
        this.t = 1;
        this.s = (x < 0) ? -1 : 0;
        if (x > 0) {
            this[0] = x;
        } else if (x < -1) {
            this[0] = x + this.DV;
        } else {
            this.t = 0;
        }
    };

    BigInteger.fromString = function (s, b) {
        var k, i = s.length, mi = false, sh = 0, x;
        if (b === 16) {
            k = 4;
        } else if (b === 8) {
            k = 3;
        } else if (b === 256) {
            // byte array
            k = 8;
        } else if (b === 2) {
            k = 1;
        } else if (b === 32) {
            k = 5;
        } else if (b === 4) {
            k = 2;
        } else {
            this.fromRadix(s, b);
            return;
        }
        this.t = 0;
        this.s = 0;
        i -= 1;
        while (i >= 0) {
            x = (k === 8) ? s[i] & 0xff : this.intAt(s, i);
            if (x < 0) {
                if (s.charAt(i) === "-") {
                    mi = true;
                }
                i = 0;
            } else {
                mi = false;
                if (sh === 0) {
                    this[this.t] = x;
                    this.t += 1;
                } else if (sh + k > this.DB) {
                    this[this.t - 1] |= (x & ((1 << (this.DB - sh)) - 1)) << sh;
                    this[this.t] = (x >> (this.DB - sh));
                    this.t += 1;
                } else {
                    this[this.t - 1] |= x << sh;
                }
                sh += k;
                if (sh >= this.DB) {
                    sh -= this.DB;
                }
            }
            i -= 1;
        }
        if (k === 8 && (s[0] & 0x80) !== 0) {
            this.s = -1;
            if (sh > 0) {
                this[this.t - 1] |= ((1 << (this.DB - sh)) - 1) << sh;
            }
        }
        this.clamp();
        if (mi) {
            BigInteger.ZERO.subTo(this, this);
        }
    };

    BigInteger.fromRadix = function (s, b) {
        this.fromInt(0);
        if (b === null || b === undefined) {
            b = 10;
        }
        var cs = this.chunkSize(b), d, mi, j, w, x, i;
        d = Math.pow(b, cs);
        mi = false;
        j = 0;
        w = 0;
        for (i = 0; i < s.length; ++i) {
            x = this.intAt(s, i);
            if (x < 0) {
                if (s.charAt(i) === "-" && this.signum() === 0) {
                    mi = true;
                }
            }
            w = b * w + x;
            if (++j >= cs) {
                this.dMultiply(d);
                this.dAddOffset(w, 0);
                j = 0;
                w = 0;
            }
        }
        if (j > 0) {
            this.dMultiply(Math.pow(b, j));
            this.dAddOffset(w, 0);
        }
        if (mi) {
            BigInteger.ZERO.subTo(this, this);
        }
    };

    BigInteger.negate = function () {
        var r = BigInteger();
        BigInteger.ZERO.subTo(this, r);
        return r;
    };

    BigInteger.addTo = function (a, r) {
        var i = 0, c = 0, m = Math.min(a.t, this.t);
        while (i < m) {
            c += this[i] + a[i];
            r[i] = c & this.DM;
            c >>= this.DB;
            i += 1;
        }
        if (a.t < this.t) {
            c += a.s;
            while (i < this.t) {
                c += this[i];
                r[i] = c & this.DM;
                c >>= this.DB;
                i += 1;
            }
            c += this.s;
        } else {
            c += this.s;
            while (i < a.t) {
                c += a[i];
                r[i] = c & this.DM;
                c >>= this.DB;
                i += 1;
            }
            c += a.s;
        }
        r.s = (c < 0) ? -1 : 0;
        if (c > 0) {
            r[i] = c;
            i += 1;
        } else if (c < -1) {
            r[i] = this.DV + c;
            i += 1;
        }
        r.t = i;
        r.clamp();
    };

    BigInteger.subTo = function (a, r) {
        var i = 0, c = 0, m = Math.min(a.t, this.t);
        while (i < m) {
            c += this[i] - a[i];
            r[i] = c & this.DM;
            c >>= this.DB;
            i += 1;
        }
        if (a.t < this.t) {
            c -= a.s;
            while (i < this.t) {
                c += this[i];
                r[i] = c & this.DM;
                c >>= this.DB;
                i += 1;
            }
            c += this.s;
        } else {
            c += this.s;
            while (i < a.t) {
                c -= a[i];
                r[i] = c & this.DM;
                c >>= this.DB;
                i += 1;
            }
            c -= a.s;
        }
        r.s = (c < 0) ? -1 : 0;
        if (c < -1) {
            r[i] = this.DV + c;
            i += 1;
        } else if (c > 0) {
            r[i] = c;
            i += 1;
        }
        r.t = i;
        r.clamp();
    };

    BigInteger.multiplyTo = function (a, r) {
        var x = this.abs(), y = a.abs(), i = x.t;
        r.t = i + y.t;
        while (--i >= 0) {
            r[i] = 0;
        }
        for (i = 0; i < y.t; ++i) {
            r[i + x.t] = x.am(0, y[i], r, i, 0, x.t);
        }
        r.s = 0;
        r.clamp();
        if (this.s !== a.s) {
            BigInteger.ZERO.subTo(r, r);
        }
    };

    BigInteger.divRemTo = function (m, q, r) {
        var pm = m.abs(), pt, y, ts, ms, nsh, ys, y0, yt, d1, d2, e, qd, i, j, t;
        if (pm.t <= 0) {
            return;
        }
        pt = this.abs();
        if (pt.t < pm.t) {
            if (q !== null) {
                q.fromInt(0);
            }
            if (r !== null) {
                this.copyTo(r);
            }
            return;
        }
        if (r === null) {
            r = BigInteger();
        }
        y = BigInteger();
        ts = this.s;
        ms = m.s;
        nsh = this.DB - this.nbits(pm[pm.t - 1]); // normalize modulus
        if (nsh > 0) {
            pm.lShiftTo(nsh, y);
            pt.lShiftTo(nsh, r);
        } else {
            pm.copyTo(y);
            pt.copyTo(r);
        }
        ys = y.t;
        y0 = y[ys - 1];
        if (y0 === 0) {
            return;
        }
        yt = y0 * (1 << this.F1) + ((ys > 1) ? y[ys - 2] >> this.F2 : 0);
        d1 = this.FV / yt;
        d2 = (1 << this.F1) / yt;
        e = 1 << this.F2;
        i = r.t;
        j = i - ys;
        t = (q === null) ? BigInteger() : q;
        y.dlShiftTo(j, t);
        if (r.compareTo(t) >= 0) {
            r[r.t] = 1;
            r.t += 1;
            r.subTo(t, r);
        }
        BigInteger.ONE.dlShiftTo(ys, t);
        t.subTo(y, y); // "negative" y so we can replace sub with am later
        while (y.t < ys) {
            y[y.t] = 0;
            y.t += 1;
        }
        while (--j >= 0) {
            // Estimate quotient digit
            qd = (r[--i] === y0) ? this.DM : Math.floor(r[i] * d1 + (r[i - 1] + e) * d2);
            r[i] += y.am(0, qd, r, j, 0, ys);
            if (r[i] < qd) { // Try it out
                y.dlShiftTo(j, t);
                r.subTo(t, r);
                while (r[i] < --qd) {
                    r.subTo(t, r);
                }
            }
        }
        if (q !== null) {
            r.drShiftTo(ys, q);
            if (ts !== ms) {
                BigInteger.ZERO.subTo(q, q);
            }
        }
        r.t = ys;
        r.clamp();
        if (nsh > 0) {
            r.rShiftTo(nsh, r); // Denormalize remainder
        }
        if (ts < 0) {
            BigInteger.ZERO.subTo(r, r);
        }
    };

    BigInteger.squareTo = function (r) {
        var x = this.abs(), i = 2 * x.t, c;
        r.t = i;
        while (--i >= 0) {
            r[i] = 0;
        }
        for (i = 0; i < x.t - 1; ++i) {
            c = x.am(i, x[i], r, 2 * i, 0, 1);
            r[i + x.t] += x.am(i + 1, 2 * x[i], r, 2 * i + 1, c, x.t - i - 1);
            if (r[i + x.t] >= x.DV) {
                r[i + x.t] -= x.DV;
                r[i + x.t + 1] = 1;
            }
        }
        if (r.t > 0) {
            r[r.t - 1] += x.am(i, x[i], r, 2 * i, 0, 1);
        }
        r.s = 0;
        r.clamp();
    };

    BigInteger.copyTo = function (r) {
        var i;
        for (i = this.t - 1; i >= 0; --i) {
            r[i] = this[i];
        }
        r.t = this.t;
        r.s = this.s;
    };

    BigInteger.drShiftTo = function (n, r) {
        var i;
        for (i = n; i < this.t; ++i) {
            r[i - n] = this[i];
        }
        r.t = Math.max(this.t - n, 0);
        r.s = this.s;
    };

    BigInteger.dlShiftTo = function (n, r) {
        var i;
        for (i = this.t - 1; i >= 0; --i) {
            r[i + n] = this[i];
        }
        for (i = n - 1; i >= 0; --i) {
            r[i] = 0;
        }
        r.t = this.t + n;
        r.s = this.s;
    };

    BigInteger.rShiftTo = function (n, r) {
        r.s = this.s;
        var ds = Math.floor(n / this.DB), bs, cbs, bm, i;
        if (ds >= this.t) {
            r.t = 0;
            return;
        }
        bs = n % this.DB;
        cbs = this.DB - bs;
        bm = (1 << bs) - 1;
        r[0] = this[ds] >> bs;
        for (i = ds + 1; i < this.t; ++i) {
            r[i - ds - 1] |= (this[i] & bm) << cbs;
            r[i - ds] = this[i] >> bs;
        }
        if (bs > 0) {
            r[this.t - ds - 1] |= (this.s & bm) << cbs;
        }
        r.t = this.t - ds;
        r.clamp();
    };

    BigInteger.lShiftTo = function (n, r) {
        var bs, cbs, bm, ds, c, i;
        bs = n % this.DB;
        cbs = this.DB - bs;
        bm = (1 << cbs) - 1;
        ds = Math.floor(n / this.DB);
        c = (this.s << bs) & this.DM;
        for (i = this.t - 1; i >= 0; --i) {
            r[i + ds + 1] = (this[i] >> cbs) | c;
            c = (this[i] & bm) << bs;
        }
        for (i = ds - 1; i >= 0; --i) {
            r[i] = 0;
        }
        r[ds] = c;
        r.t = this.t + ds + 1;
        r.s = this.s;
        r.clamp();
    };

    BigInteger.compareTo = function (a) {
        var r = this.s - a.s, i;
        if (r !== 0) {
            return r;
        }
        i = this.t;
        r = i - a.t;
        if (r !== 0) {
            return (this.s < 0) ? -r : r;
        }
        while (--i >= 0) {
            if (this[i] - a[i] !== 0) {
                r = this[i] - a[i];
                return r;
            }
        }
        return 0;
    };

    BigInteger.int2char = function(n) {
        return BI_RM.charAt(n);
    };

    BigInteger.toString = function (b) {
        if (this.s < 0) {
            return "-" + this.negate().toString(b);
        }
        var k, km, d, m = false, r = "", i = this.t, p;
        if (b === 16) {
            k = 4;
        } else if (b === 8) {
            k = 3;
        } else if (b === 2) {
            k = 1;
        } else if (b === 32) {
            k = 5;
        } else if (b === 4) {
            k = 2;
        } else {
            return this.toRadix(b);
        }
        km = (1 << k) - 1;
        p = this.DB - (i * this.DB) % k;
        if (i-- > 0) {
            d = this[i] >> p;
            if (p < this.DB && d > 0) {
                m = true;
                r = this.int2char(d);
            }
            while (i >= 0) {
                if (p < k) {
                    d = (this[i] & ((1 << p) - 1)) << (k - p);
                    p += this.DB - k;
                    d |= this[--i] >> p;
                } else {
                    p -= k;
                    d = (this[i] >> p) & km;
                    if (p <= 0) {
                        p += this.DB;
                        --i;
                    }
                    if (d > 0) {
                        m = true;
                    }
                    if (m) {
                        r += this.int2char(d);
                    }
                }
            }
        }
        return m ? r : "0";
    };

    BigInteger.toRadix = function (b) {
        if (b === null || b === undefined) {
            b = 10;
        }
        if (this.signum() === 0 || b < 2 || b > 36) {
            return "0";
        }
        var cs = this.chunkSize(b), a = Math.pow(b, cs), d = this.nbv(a), r = "", y, z;
        y = BigInteger();
        z = BigInteger();
        this.divRemTo(d, y, z);
        while (y.signum() > 0) {
            r = (a + z.intValue()).toString(b).substr(1) + r;
            y.divRemTo(d, y, z);
        }
        return z.intValue().toString(b) + r;
    };

    BigInteger.nbits = function (x) {
        var r = 1, t;
        t = x >>> 16;
        if (t !== 0) {
            x = t;
            r += 16;
        }
        t = x >>> 8;
        if (t !== 0) {
            x = t;
            r += 8;
        }
        t = x >>> 4;
        if (t !== 0) {
            x = t;
            r += 4;
        }
        t = x >>> 2;
        if (t !== 0) {
            x = t;
            r += 2;
        }
        t = x >>> 1;
        if (t !== 0) {
            x = t;
            r += 1;
        }
        return r;
    };

    BigInteger.abs = function () {
        return (this.s < 0) ? this.negate() : this;
    };

    BigInteger.clamp = function () {
        var c = this.s & this.DM;
        while (this.t > 0 && this[this.t - 1] === c) {
            --this.t;
        }
    };

    BigInteger.chunkSize = function (r) {
        return Math.floor(Math.LN2 * this.DB / Math.log(r));
    };

    BigInteger.intAt = function (s, i) {
        var c = BI_RC[s.charCodeAt(i)];
        return (c === undefined) ? -1 : c;
    };

    BigInteger.intValue = function () {
        if (this.s < 0) {
            if (this.t === 1) {
                return this[0] - this.DV;
            }
            if (this.t === 0) {
                return -1;
            }
        } else if (this.t === 1) {
            return this[0];
        }
        if (this.t === 0) {
            return 0;
        }
        // assumes 16 < dbits < 32
        return ((this[1] & ((1 << (32 - this.DB)) - 1)) << this.DB) | this[0];
    };

    BigInteger.dMultiply = function (n) {
        this[this.t] = this.am(0, n - 1, this, 0, 0, this.t);
        ++this.t;
        this.clamp();
    };

    BigInteger.am = function (i, x, w, j, c, n) {
        var xl = x & 0x3fff, xh = x >> 14, l, h, m;
        while (--n >= 0) {
            l = this[i] & 0x3fff;
            h = this[i++] >> 14;
            m = xh * l + h * xl;
            l = xl * l + ((m & 0x3fff) << 14) + w[j] + c;
            c = (l >> 28) + (m >> 14) + xh * h;
            w[j++] = l & 0xfffffff;
        }
        return c;
    };

    BigInteger.dAddOffset = function (n, w) {
        if (n === 0) {
            return;
        }
        while (this.t <= w) {
            this[this.t++] = 0;
        }
        this[w] += n;
        while (this[w] >= this.DV) {
            this[w] -= this.DV;
            if (++w >= this.t) {
                this[this.t++] = 0;
            }
            ++this[w];
        }
    };

    BigInteger.signum = function () {
        if (this.s < 0) {
            return -1;
        }
        if (this.t <= 0 || (this.t === 1 && this[0] <= 0)) {
            return 0;
        }
        return 1;
    };

    BigInteger.add = function (a) {
        var r = BigInteger();
        this.addTo(a, r);
        return r;
    };

    BigInteger.subtract = function (a) {
        var r = BigInteger();
        this.subTo(a, r);
        return r;
    };

    BigInteger.multiply = function (a) {
        var r = BigInteger();
        this.multiplyTo(a, r);
        return r;
    };

    BigInteger.divide = function (a) {
        var r = BigInteger();
        this.divRemTo(a, r, null);
        return r;
    };

    BigInteger.square = function () {
        var r = BigInteger();
        this.squareTo(r);
        return r;
    };

    BigInteger.exp = function (e, z) {
        if (e > 0xffffffff || e < 1) {
            return BigInteger.ONE;
        }
        var r = BigInteger(), r2, g = z.convert(this), i = this.nbits(e) - 1, t;
        r2 = BigInteger();
        g.copyTo(r);
        while (--i >= 0) {
            z.sqrTo(r, r2);
            if ((e & (1 << i)) > 0) {
                z.mulTo(r2, g, r);
            } else {
                t = r;
                r = r2;
                r2 = t;
            }
        }
        return z.revert(r);
    };

    BigInteger.equals = function (a) {
        return (this.compareTo(a) === 0);
    };

    BigInteger.shiftLeft = function (n) {
        var r = BigInteger();
        if (n < 0) {
            this.rShiftTo(-n, r);
        } else {
            this.lShiftTo(n, r);
        }
        return r;
    };

    BigInteger.shiftRight = function (n) {
        var r = BigInteger();
        if (n < 0) {
            this.lShiftTo(-n, r);
        } else {
            this.rShiftTo(n, r);
        }
        return r;
    };

    BigInteger.modPow = function (e, m) {
        var i = e.bitLength(), k, r, z, g = [], n = 3, k1, km, j, w, is1, r2, t, g2;
        r = this.nbv(1);
        if (i <= 0) {
            return r;
        }
        if (i < 18) {
            k = 1;
        } else if (i < 48) {
            k = 3;
        } else if (i < 144) {
            k = 4;
        } else if (i < 768) {
            k = 5;
        } else {
            k = 6;
        }
        if (i < 8) {
            z = new Classic(m);
        } else if (m.isEven()) {
            z = new Barrett(m);
        } else {
            z = new Montgomery(m);
        }
        // precomputation
        k1 = k - 1;
        km = (1 << k) - 1;
        g[1] = z.convert(this);
        if (k > 1) {
            g2 = BigInteger();
            z.sqrTo(g[1], g2);
            while (n <= km) {
                g[n] = BigInteger();
                z.mulTo(g2, g[n - 2], g[n]);
                n += 2;
            }
        }
        j = e.t - 1;
        is1 = true;
        r2 = BigInteger();
        i = this.nbits(e[j]) - 1;
        while (j >= 0) {
            if (i >= k1) {
                w = (e[j] >> (i - k1)) & km;
            } else {
                w = (e[j] & ((1 << (i + 1)) - 1)) << (k1 - i);
                if (j > 0) {
                    w |= e[j - 1] >> (this.DB + i - k1);
                }
            }
            n = k;
            while ((w & 1) === 0) {
                w >>= 1;
                --n;
            }
            i -= n;
            if (i < 0) {
                i += this.DB;
                --j;
            }
            if (is1) { // ret == 1, don't bother squaring or multiplying it
                g[w].copyTo(r);
                is1 = false;
            } else {
                while (n > 1) {
                    z.sqrTo(r, r2);
                    z.sqrTo(r2, r);
                    n -= 2;
                }
                if (n > 0) {
                    z.sqrTo(r, r2);
                } else {
                    t = r;
                    r = r2;
                    r2 = t;
                }
                z.mulTo(r2, g[w], r);
            }
            while (j >= 0 && (e[j] & (1 << i)) === 0) {
                z.sqrTo(r, r2);
                t = r;
                r = r2;
                r2 = t;
                if (--i < 0) {
                    i = this.DB - 1;
                    --j;
                }
            }
        }
        return z.revert(r);
    };

    BigInteger.bitLength = function () {
        if (this.t <= 0) {
            return 0;
        }
        return this.DB * (this.t - 1) + this.nbits(this[this.t - 1] ^ (this.s & this.DM));
    };

    BigInteger.mod = function (a) {
        var r = BigInteger();
        this.abs().divRemTo(a, null, r);
        if (this.s < 0 && r.compareTo(BigInteger.ZERO) > 0) {
            a.subTo(r, r);
        }
        return r;
    };

    BigInteger.isEven = function () {
        return ((this.t > 0) ? (this[0] & 1) : this.s) === 0;
    };

    BigInteger.invDigit = function () {
        if (this.t < 1) {
            return 0;
        }
        var x = this[0], y;
        if ((x & 1) === 0) {
            return 0;
        }
        y = x & 3; // y == 1/x mod 2^2
        y = (y * (2 - (x & 0xf) * y)) & 0xf; // y == 1/x mod 2^4
        y = (y * (2 - (x & 0xff) * y)) & 0xff; // y == 1/x mod 2^8
        y = (y * (2 - (((x & 0xffff) * y) & 0xffff))) & 0xffff; // y == 1/x mod 2^16
        // last step - calculate inverse mod (1<<dbits) directly;
        // assumes 16 < dbits <= 32 and assumes ability to handle 48-bit ints
        y = (y * (2 - x * y % this.DV)) % this.DV; // y == 1/x mod 2^dbits
        // we really want the negative inverse, and -(1<<dbits) < y < (1<<dbits)
        return (y > 0) ? this.DV - y : -y;
    };

    BigInteger.toByteArray = function () {
        var i = this.t, r = [], p, d, k = 0;
        r[0] = this.s;
        p = this.DB - (i * this.DB) % 8;
        if (i-- > 0) {
            d = this[i] >> p;
            if (p < this.DB && d !== (this.s & this.DM) >> p) {
                r[k++] = d | (this.s << (this.DB - p));
            }
            while (i >= 0) {
                if (p < 8) {
                    d = (this[i] & ((1 << p) - 1)) << (8 - p);
                    p += this.DB - 8;
                    d |= this[--i] >> p;
                } else {
                    p -= 8;
                    d = (this[i] >> p) & 0xff;
                    if (p <= 0) {
                        p += this.DB;
                        --i;
                    }
                }
                if ((d & 0x80) !== 0) {
                    d |= -256;
                }
                if (k === 0 && (this.s & 0x80) !== (d & 0x80)) {
                    ++k;
                }
                if (k > 0 || d !== this.s) {
                    r[k++] = d;
                }
            }
        }
        return r;
    };

    BigInteger.modInverse = function (m) {
        var ac = m.isEven(), u, v, a, b, c, d;
        if ((this.isEven() && ac) || m.signum() === 0) {
            return BigInteger.ZERO;
        }
        u = m.clone();
        v = this.clone();
        a = this.nbv(1);
        b = this.nbv(0);
        c = this.nbv(0);
        d = this.nbv(1);
        while (u.signum() !== 0) {
            while (u.isEven()) {
                u.rShiftTo(1, u);
                if (ac) {
                    if (!a.isEven() || !b.isEven()) {
                        a.addTo(this, a);
                        b.subTo(m, b);
                    }
                    a.rShiftTo(1, a);
                } else if (!b.isEven()) {
                    b.subTo(m, b);
                }
                b.rShiftTo(1, b);
            }
            while (v.isEven()) {
                v.rShiftTo(1, v);
                if (ac) {
                    if (!c.isEven() || !d.isEven()) {
                        c.addTo(this, c);
                        d.subTo(m, d);
                    }
                    c.rShiftTo(1, c);
                } else if (!d.isEven()) {
                    d.subTo(m, d);
                }
                d.rShiftTo(1, d);
            }
            if (u.compareTo(v) >= 0) {
                u.subTo(v, u);
                if (ac) {
                    a.subTo(c, a);
                }
                b.subTo(d, b);
            } else {
                v.subTo(u, v);
                if (ac) {
                    c.subTo(a, c);
                }
                d.subTo(b, d);
            }
        }
        if (v.compareTo(BigInteger.ONE) !== 0) {
            return BigInteger.ZERO;
        }
        if (d.compareTo(m) >= 0) {
            return d.subtract(m);
        }
        if (d.signum() < 0) {
            d.addTo(m, d);
        } else {
            return d;
        }
        if (d.signum() < 0) {
            return d.add(m);
        }
        return d;
    };

    BigInteger.clone = function () {
        var r = BigInteger();
        this.copyTo(r);
        return r;
    };

    BigInteger.testBit = function (n) {
        var j = Math.floor(n / this.DB);
        if (j >= this.t) {
            return (this.s !== 0);
        }
        return ((this[j] & (1 << (n % this.DB))) !== 0);
    };

    BigInteger.pow = function (e) {
        return this.exp(e, new NullExponent());
    };

    BigInteger.multiplyLowerTo = function (a, n, r) {
        var i = Math.min(this.t + a.t, n), j;
        r.s = 0; // assumes a,this >= 0
        r.t = i;
        while (i > 0) {
            r[--i] = 0;
        }
        for (j = r.t - this.t; i < j; ++i) {
            r[i + this.t] = this.am(0, a[i], r, i, 0, this.t);
        }
        for (j = Math.min(a.t, n); i < j; ++i) {
            this.am(0, a[i], r, i, 0, n - i);
        }
        r.clamp();
    };

    BigInteger.multiplyUpperTo = function (a, n, r) {
        --n;
        var i = r.t = this.t + a.t - n;
        r.s = 0; // assumes a,this >= 0
        while (--i >= 0) {
            r[i] = 0;
        }
        for (i = Math.max(n - this.t, 0); i < a.t; ++i) {
            r[this.t + i - n] = this.am(n - i, a[i], r, 0, 0, this.t + i - n);
        }
        r.clamp();
        r.drShiftTo(1, r);
    };

    BigInteger.prototype.nbv = BigInteger.nbv;
    BigInteger.prototype.fromNumber = BigInteger.fromNumber;
    BigInteger.prototype.fromInt = BigInteger.fromInt;
    BigInteger.prototype.fromString = BigInteger.fromString;
    BigInteger.prototype.fromRadix = BigInteger.fromRadix;
    BigInteger.prototype.negate = BigInteger.negate;
    BigInteger.prototype.addTo = BigInteger.addTo;
    BigInteger.prototype.subTo = BigInteger.subTo;
    BigInteger.prototype.multiplyTo = BigInteger.multiplyTo;
    BigInteger.prototype.divRemTo = BigInteger.divRemTo;
    BigInteger.prototype.squareTo = BigInteger.squareTo;
    BigInteger.prototype.copyTo = BigInteger.copyTo;
    BigInteger.prototype.drShiftTo = BigInteger.drShiftTo;
    BigInteger.prototype.dlShiftTo = BigInteger.dlShiftTo;
    BigInteger.prototype.rShiftTo = BigInteger.rShiftTo;
    BigInteger.prototype.lShiftTo = BigInteger.lShiftTo;
    BigInteger.prototype.compareTo = BigInteger.compareTo;
    BigInteger.prototype.int2char = BigInteger.int2char;
    BigInteger.prototype.toString = BigInteger.toString;
    BigInteger.prototype.toRadix = BigInteger.toRadix;
    BigInteger.prototype.nbits = BigInteger.nbits;
    BigInteger.prototype.abs = BigInteger.abs;
    BigInteger.prototype.clamp = BigInteger.clamp;
    BigInteger.prototype.chunkSize = BigInteger.chunkSize;
    BigInteger.prototype.intAt = BigInteger.intAt;
    BigInteger.prototype.intValue = BigInteger.intValue;
    BigInteger.prototype.dMultiply = BigInteger.dMultiply;
    BigInteger.prototype.am = BigInteger.am;
    BigInteger.prototype.dAddOffset = BigInteger.dAddOffset;
    BigInteger.prototype.signum = BigInteger.signum;
    BigInteger.prototype.add = BigInteger.add;
    BigInteger.prototype.subtract = BigInteger.subtract;
    BigInteger.prototype.multiply = BigInteger.multiply;
    BigInteger.prototype.divide = BigInteger.divide;
    BigInteger.prototype.square = BigInteger.square;
    BigInteger.prototype.exp = BigInteger.exp;
    BigInteger.prototype.equals = BigInteger.equals;
    BigInteger.prototype.shiftLeft = BigInteger.shiftLeft;
    BigInteger.prototype.shiftRight = BigInteger.shiftRight;
    BigInteger.prototype.modPow = BigInteger.modPow;
    BigInteger.prototype.bitLength = BigInteger.bitLength;
    BigInteger.prototype.mod = BigInteger.mod;
    BigInteger.prototype.isEven = BigInteger.isEven;
    BigInteger.prototype.invDigit = BigInteger.invDigit;
    BigInteger.prototype.toByteArray = BigInteger.toByteArray;
    BigInteger.prototype.modInverse = BigInteger.modInverse;
    BigInteger.prototype.clone = BigInteger.clone;
    BigInteger.prototype.testBit = BigInteger.testBit;
    BigInteger.prototype.pow = BigInteger.pow;
    BigInteger.prototype.multiplyLowerTo = BigInteger.multiplyLowerTo;
    BigInteger.prototype.multiplyUpperTo = BigInteger.multiplyUpperTo;
    BigInteger.prototype.DB = dbits;
    BigInteger.prototype.DM = ((1 << dbits) - 1);
    BigInteger.prototype.DV = (1 << dbits);
    BigInteger.prototype.FV = Math.pow(2, BI_FP);
    BigInteger.prototype.F1 = BI_FP - dbits;
    BigInteger.prototype.F2 = 2 * dbits - BI_FP;

    //CONSTANTS
    BigInteger.ZERO = BigInteger.nbv(0);
    BigInteger.ONE = BigInteger.nbv(1);

    return BigInteger;
}());